package com.singzi.leetcode.N1700;

import com.singzi.leetcode.obj.TreeNode;

import java.util.*;

public class T1609 {
    public static void main(String[] args) {
        Solution1609 solution1609 = new Solution1609();
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(10);
        treeNode.right = new TreeNode(4);
        treeNode.left = new TreeNode(10);
    }
}
class Solution1609 {
    public boolean isEvenOddTree(TreeNode root) {
        int numsLayer = 1;
        int temp = -1;
        boolean isOdd = true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            if(numsLayer==0){
                isOdd = !isOdd;
            }
            TreeNode treeNode = queue.remove();
            numsLayer--;
            if(isOdd){
                if (treeNode.val % 2 == 0) return false;
            } else {
                if (treeNode.val % 2 != 0) return false;
            }
            if(temp != -1 && isOdd){
                if(temp > treeNode.val) return false;
            }
            if(temp != -1 && !isOdd){
                if(temp < treeNode.val) return false;
            }
            temp = treeNode.val;
            if(treeNode.left != null) {
                queue.add(treeNode.left);
                numsLayer++;
            }
            if(treeNode.right != null) {
                queue.add(treeNode.right);
                numsLayer++;
            }
        }
        return true;
    }
    public boolean isEvenOddTree1(TreeNode root) {
        int numTree = 1;
        int numLayer = 2;
        boolean isOdd = true;
        int temp = -1;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            if (numTree == numLayer) {
                isOdd = !isOdd;
                numLayer = 2 * numLayer;
                temp = -1;
            }
            TreeNode treeNode = queue.remove();
            numTree++;
            if(treeNode == null){
                queue.add(null);
                queue.add(null);
            }
            queue.add(treeNode.left != null?treeNode.left: null);
            queue.add(treeNode.right !=null? treeNode.right:null);
        }
        return true;
    }
}